Інститут менеджменту та економіки „Галицька Академія” Кафедра програмного забезпечення та штучного інтелекту КУРСОВА РОБОТА з дисципліни: “Основи дискретної математики” Тема – Застосування формул включень і виключень та розбиття для розв’язування задач в дискретній математиці. ПОЯСНЮВАЛЬНА ЗАПИСКА КР.ПЗ- 21. 00. 00. 000. ПЗ Студент групи ПЗ-04-1 __________ (Кайданська Н.В) (підпис) Допускається до захисту Керівник курсового проекту Доцент (Плотніков В. Г.) (посада) (підпис) (дата) (розшифровка підпису) м. Івано-Франківськ 2004  Анотація В курсовій роботі проаналізовані основні поняття і властивості формул включень і виключень та розбиття і розв’язання певних типів задач. Summary In the term paper there are the analysed basic concepts and properties of formulas inclusions and deenergizings and decision and unbind certain type of tasks. ЗМІСТ Вступ 1. Розбиття. ................................................................................................... 2. Поліномна формула. 3. Формула включень і виключень. ..................................................... 4. Розв’язування задач на розбиття................................................ 5. Застосування формули включень і виключень для розв’язування задач......................................................................... Висновки.................................................................................. Перелік використаних літературних джерел........................ Вступ Комбінаторика – це наука, основним завданням якої є перерахунок і перелічення елементів у скінчених множинах. Якщо в задачі визначається, скільки елементів, які належать заданій скінченій множині, мають деяку властивість або заданий набір властивостей, то ця задача називається задачею перерахунку. В інших випадках для яких-небудь цілей треба вилучити всі елементи множини, які задовольняють задані властивості. Такі задачі називаються задачами перелічення. Зустрічаються також задачі, коли на початковій скінченій множині елементів означено деяку цільову функцію, причому інтерес становлять елементи множини, що забезпечують мінімальне (або максимальне) значення цієї функції. У цьому разі маємо окремий випадок задачі оптимізації. Тут під її розв’язком у сильному значенні розуміють знаходження сукупності всіх елементів, які забезпечують мінімальне (або максимальне) значення цільової функції, а під розв’язком у слабкому значенні – відшукання довільного елемента, що забезпечує мінімальне (або максимальне) значення цільової функції. Іноді цікавляться лише мінімальним (або максимальним) значенням функції. Усі зазначені задачі пов’язані одна з одною. Так, при розв’язуванні задач оптимізації припускається, що в розпорядженні є метод перелічення елементів початкової множини (яка, як правило, є сукупністю елементів деякої великої множини, що задовольняє задану властивість), а для того щоб оцінити ефективність методів перелічення або оптимізації, часто доцільно розв’язувати задачу перерахунку елементів (у початковій множині або в деяких її підмножинах. Розбиття. Сукупність множин А1, А2, ..., Аn називається розбиттям множини А, якщо: n 1.U Аі = А i=1 2.Аі∩Аj = ( (i(j. Підрахуємо число розбиттів скінченої множини Х, де (Х(= n, на k підмножин Х1,Х2,..., Хn(k(1), де k (ni = n, таких, що кожне Хі містить ni елементів, тобто, i=1 k U Хі = Х, Хі∩Хj = Ø при i ≠ j, │Xi│= ni, i=1,2,…,k. (1.1) i=1 Нехай для деяких номерів і матимемо Хі = Ø. Число зазначених розбиттів при фіксованих ni позначимо через Cnⁿ1···ⁿk . У цьому випадку набір підмножин множини Х у розбитті є впорядков...